package com.zj.leetcode.medium.dynamicProgramming;

/**
 * @program: algorithm
 * @description:
 * 解码方法
 * 91 decode-ways
 * @author: Zhang Bo
 * @create: 2022-05-07 11:28:59
 **/
public class DecodeWays {
    public static void main(String[] args) {
        Solution solution = new DecodeWays().new Solution();

        String[] strs = new String[]{"220", "06", "0", "10", "1123", "11212"};
        for (String str : strs) {
            System.out.println(solution.numDecodings(str));
        }

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 123 4
         * f(n) = f(n - 1) + f(n - 1) - f(n - 2)
         *
         * @param s
         * @return
         */
        public int numDecodings(String s) {
            final int length = s.length();
            if(length == 0) return 0;
            if(s.charAt(0) == '0') return 0;

            int[] dp = new int[length+1];
            dp[0] = 1;

            for(int i=0;i<length;i++){
                dp[i+1] = s.charAt(i)=='0'?0:dp[i];
                if(i > 0 && (s.charAt(i-1) == '1' || (s.charAt(i-1) == '2' && s.charAt(i) <= '6'))){
                    dp[i+1] += dp[i-1];
                }
            }

            return dp[length];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
